# 67/100 二分查找-寻找旋转排序数组中的最小值
# leetcode第153题: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/2/7
from leetcode import test


def findMin(nums: list[int]) -> int:
    """
    [nums[k], -----, nums[n], nums[0] ------- nums[k-1]]
    """
    n = len(nums)
    l, r = 0, n - 1
    while l < r:
        mid = ((r - l) >> 1) + l
        if nums[mid] < nums[r]:
            r = mid
        else:
            l = mid + 1
    return nums[l]


if __name__ == '__main__':
    inp = [{"nums": [3, 4, 5, 1, 2]},
           {"nums": [4, 5, 6, 7, 0, 1, 2]},
           {"nums": [11, 13, 15, 17]},
           ]
    out = [1, 0, 11]
    test.test_function(findMin, inp, out)
